#include "../tools.h"


class Solution {
public:
    // void helper(vector<vector<int>>& res, vector<int>& route, int first, int n){
    //     if(first == n) {
    //         res.push_back(route);
    //         return;
    //     }

    //     for(int i = first; i < n; ++i){
    //         swap(route[i], route[first]);
    //         helper(res, route, first + 1, n);
    //         swap(route[i], route[first]);
    //     }
    // }

    void helper(vector<vector<int>>& res, vector<int>& route, vector<bool>& vis, const vector<int>& nums){
        if(route.size() == nums.size()){
            res.push_back(route);
            return;
        }

        for(int i = 0; i < nums.size(); ++i){
            if(vis[i]) continue;

            route.push_back(nums[i]);
            vis[i] = true;
            helper(res, route, vis, nums);
            route.pop_back();
            vis[i] = false;

            while(i + 1 < nums.size() && nums[i + 1] == nums[i]) ++i;
        }
    }

    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        int size = nums.size();
        if(size == 0) return res;
        if(size == 1) {
            res.push_back(nums);
            return res;
        }

        // helper(res, nums, 0, size);

        sort(nums.begin(), nums.end());
        vector<int> route;
        vector<bool> vis(nums.size(), false);
        helper(res, route, vis, nums);

        return res;
    }
};


int main(int argc, char const *argv[])
{
    Solution sol;

    vector<int> nums = {1, 0, 0, 0, 9};
    auto res = sol.permute(nums);

    show(res);


    return 0;
}
